<!-- directive:title guosy::函数尾调用 -->
<!-- directive:breadcrumb ext经验条 -->
<div class="panel-body">
    <p></p>
    <p>什么是尾调用</p>
    <p>尾调用（Tail Call）是函数式编程的一个重要概念，本身非常简单，一句话就能说清楚。就是指某个函数的最后一步是调用另一个函数。</p>
    <script type="text/xianjs" ui-bs>
        function g(x){ console.log(x); }
        function f(x){ return g(x); }
        console.log(f(1));
        //上面代码中，函数f的最后一步是调用函数g，这就是尾调用。
    </script>
    <p>尾调用不一定出现在函数尾部，只要是最后一步操作即可。</p>
    <script type="text/xianjs" ui-bs>
        function f(x){ if(x > 0){ return g(x); } return g(x) }
    </script>
    <p>尾调用优化</p>
    <p>我们知道，函数调用会在内存形成一个‘调用记录’，又称“调用帧”（call frame） ，保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用帧上方，还会形成一个B的调用帧。等到B运行结束，将结果返回到A，B的调用帧才会消失。如果函数B内部内部还要调用函数C那么还有一个C的调用帧，以此类推。所有的调用帧，就行成了一个“调用栈”（call stack）。</p>
    <p>调用由于是函数的最后一步操作，所以不需要保留外层函数的调用帧，因为调用位置，内部变量等信息都不会再用到了，只要直接用内层函数的调用帧，取代外层函数的调用帧就可以了。</p>
    <script type="text/xianjs" ui-bs>
        function g(x){ console.log(x); }
        function f(){ let m = 1; let n = 2; return g(m + n); }
        f();
        //等同于
        function f(){ return g(3); }
        f();
        //等同于
        g(3);
    </script>
    <p>上面代码中，如果函数g不是尾调用，函数f就需要保存内部的变量m和n的值，g的调用位置等信息。但由于调用g之后，函数f就结束了，所以执行到最后一步，完成可以删除f(x)的的调用帧，只保留g(3)的调用帧。</p>
    <p>这就叫做"尾调用优化",即只保留内层函数的调用帧.如果所有函数都是尾调用,那么完全可以做到。每次执行时,调用帧只有一项,这将大大节省内存.这就是"尾调用优化"的意义。</p>
    <p>注意,只有不再用到外层函数的内部变量,内层函数的调用帧才会取代外层函数的调用帧,否则就无法进行"尾调用优化"</p>
    <p>尾递归</p>
    <p>函数调用自身，称为递归。如果尾调用自身，就称为尾递归。递归非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生栈溢出错误。但是队伍尾递归来说，由于只存在一个调用帧，所以永远不会发生栈溢出错误。</p>
    <script type="text/xianjs" ui-bs>
        function factorial(n){ if(n === 1){ return 1; } return n * factorial(n - 1); }
    </script>
    <p>上面代码是一个阶乘函数，计算n的阶乘，最多需要保存n个调用数据，复杂度为O（n），如果改写成尾调用，只保留一个调用记录，复杂度为O（1）</p>
    <script type="text/xianjs" ui-bs>
        function factor(n,total){ if( n === 1){ return total; } return factor(n - 1, n * total); }
    </script>
    <p>Fibonacci数列也是可以用于尾调用。</p>
    <script type="text/xianjs" ui-bs>
        function Fibonacci(n){ if(n <= 1){ return 1; } return Fibonacci(n - 1) + Fibonacci(n - 2); }
        //尾递归
        function Fibona(n,ac1 = 1,ac2 = 1){ if(n <= 1){ return ac2; } return Fibona(n - 1,ac2 , ac1 + ac2); }
    </script>
    <p>由此可见，“尾调用优化”对递归操作意义重大，所以一些函数式编程语言将其写入了语言规格，ES6是如此，第一次明确规定，所有ECMAscript的实现，都必须部署“尾调用优化”，也就是说，ES6中只要使用尾递归，就不会发生栈溢出，相对节省内存。</p>
    <p>递归函数的改写</p>
    <p>尾递归的实现，往往需要改写递归函数，确保最后一步只调用自身。做到这一点的方法，就是把所有用到的内部变量改写成函数的参数。比如上面的例子，阶乘函数factorial需要用到一个中间变量total，那就把这个中间变量改写成函数的参数，这样做的缺点就是不太直观，第一眼很难看出来，为什么计算5的阶乘，需要传入两个参数5和1。</p>
    <script type="text/xianjs" ui-bs>
        function tailFactorial(n,total){ if( n === 1 ){ return total; } return tailFactorial(n - 1, n * total); }
        function factorial(n){ return tailFactorial(n , 1); }
        console.log(factorial(5));
        //上面代码通过一个正常形式的阶乘函数factorial，调用尾递归函数tailFactorial。看起来就正常多了。
    </script>
    <p>函数式编程中有一个概念，叫做柯里化（curring）意思是将多参数的函数转换成单参数的形式，这里也可以使用柯里化。</p>
    <script type="text/xianjs" ui-bs>
        function curring(fn,n){ return function (m){ return fn.call(this,m,n); } }
        function tailFactorial (n,total){ if( n === 1){ return total; } return tailFactorial(n - 1 , n * total); }
        const factorial = curring(tailFactorial,1);
        console.log(factorial(5));
    </script>
    <p>第二种方法就简单多了，就是采用ES6的函数默认值。</p>
    <script type="text/xianjs" ui-bs>
        function factorial(n,total = 1){ if( n === 1){ return total; } return factorial(n - 1 , n * total); }
        console.log(factorial(5));
    </script>
    <p>上面代码中，参数total有默认值1，所以调用时不用提供这个值</p>
    <p>总结一下，递归本质上是一种循环造作，纯粹的函数式编程语言没有循环操作命令，所有的循环都用递归实现，这就是为什么尾递归对这些语言极为重要，对于其他支持“尾递归优化”的语言，只需要知道循环可以用递归代替，而不但使用递归，就最好使用尾递归。</p>
</div>